﻿///////////////////////////////////////////////////////////////////////////////
//
//  This file is part of MathLib.NET.
//
//  This library is free software; you can redistribute it and/or
//  modify it under the terms of the GNU Lesser General Public
//  License as published by the Free Software Foundation; either
//  version 2.1 of the License, or (at your option) any later version.
//  
//  This library is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//  Lesser General Public License for more details.
//  
//  You should have received a copy of the GNU Lesser General Public
//  License along with this library;  If not, see 
//  <http://www.gnu.org/licenses/>.
//
///////////////////////////////////////////////////////////////////////////////

using System;
using System.Collections.Generic;
using System.Collections;

namespace MathLib
{
    /// <summary>
    /// Integer factorization class.
    /// </summary>
    public class IntegerFactorize : IEnumerable<uint>
    {
        private static List<uint> mPrimes = new List<uint>();
        private uint mNextNum = 2;

        public IntegerFactorize()
        {
            mPrimes.Add(mNextNum);
        }

        public IList<uint> GetPrimeList()
        {
            return mPrimes;
        }

        public void ClearPrimes()
        {
            mPrimes.Clear();
            mPrimes.Add(2);
            mNextNum = 1;
        }

        public bool IsPrime(uint checkValue)
        {
            // Search for prime in cached list
            foreach (uint prime in mPrimes)
            {
                if (checkValue == prime)
                    return true; // found prime
                else if (prime > checkValue)
                    return false; // found non-prime
            }

            // Search for prime
            while (mNextNum <= checkValue)
            {
                mNextNum += 2;

                if (IsNextPrime(mNextNum))
                {
                    mPrimes.Add(mNextNum);
                    return true; // found prime
                }
            }

            return false; // found non-prime
        }

        private bool IsNextPrime(uint checkValue)
        {
            bool isPrime = true;

            foreach (uint prime in mPrimes)
            {
                if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
                {
                    isPrime = false;
                    break;
                }
            }

            return isPrime;
        }

        public IEnumerator<uint> GetEnumerator()
        {
            foreach (uint prime in mPrimes)
            {
                yield return prime;
            }

            while (mNextNum < int.MaxValue)
            {
                mNextNum++;

                if (IsNextPrime(mNextNum))
                {
                    mPrimes.Add(mNextNum);
                    yield return mNextNum;
                }
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public IEnumerable<uint> FindFactors(uint value)
        {
            List<uint> factors = new List<uint>();

            foreach (uint prime in this)
            {
                while (value % prime == 0)
                {
                    value /= prime;
                    factors.Add(prime);
                }

                if (value == 1)
                {
                    break;
                }
            }

            return factors;
        }
    }
}
